Slide 2: Time Complexity

Defining Time Complexity: The Big $O$ Notation

Algorithm Analysis quantifies the resource requirements (time and space) of an algorithm relative to the size of the input ( $N$ ).

We use Big $O$ Notation ( $O(f(N))$ ) to describe the worst-case rate of growth (upper bound) of an algorithm's running time as $N \to \infty$ .

Key Principles of Big $O$ Analysis:

Focus on Dominant Terms: Drop lower-order terms (e.g., $N^2 + N$ becomes $O(N^2)$ ).
Ignore Constants: Drop multiplicative constants (e.g., $5N^2$ becomes $O(N^2)$ ).
Worst Case: We generally calculate the performance based on the scenario that maximizes operations.

Big $O$ Calculation Cheat Sheet

$O(1)$ Check: If the code execution time does not depend on the input size $N$ (e.g., arithmetic, assignment, array lookup), it is $O(1)$ .
Loop Rule (Multiplication): If Loop A ( $O(A)$ ) contains Loop B ( $O(B)$ ), the complexity is $O(A \times B)$ . If $B$ is a constant, the complexity remains $O(A)$ .
Sequential Rule (Addition): If operation A ( $O(A)$ ) is followed by operation B ( $O(B)$ ), the complexity is $O(\text{max}(A, B))$ .
Logarithmic Hint: Any algorithm that repeatedly halves the search space (e.g., dividing $N$ by 2 each step) is $O(\log N)$ .

Standard Time Complexity Classes

Understanding these fundamental growth rates is crucial for efficient system design. Note the difference in scale!

Notation	Name	Growth Rate (N=1 Million)	Example Operation
$O(1)$	Constant	Instantaneous	Array Index Access (arr[i])
$O(\log N)$	Logarithmic	Very Fast (20 Ops)	Binary Search
$O(N)$	Linear	1 Million Ops	Single Loop Iteration
$O(N \log N)$	Log-Linear	~20 Million Ops	Efficient Sorting (Merge Sort)
$O(N^2)$	Quadratic	1 Trillion Ops	Nested Loops (Brute Force)

📝 Interactive Quiz

1. Analyze the following Python snippet. Assume `N` is the length of the list `data`.

def example_function(data):
    N = len(data)
    total = 0
    # Outer Loop: Runs N times
    for i in range(N):
        # Inner Loop: Runs a constant 5 times
        for j in range(5):
            total += data[i]

What is the Big $O$ time complexity of `example_function`?

A) $O(N^2)$
B) $O(N)$
C) $O(5N)$
D) $O(1)$

2. An algorithm has two sequential parts: one is $O(N)$ and the other is $O(N^2)$ . What is the overall time complexity?

A) $O(N)$
B) $O(N^2)$
C) $O(N + N^2)$
D) $O(N^3)$

3. Which of the following complexity classes represents the fastest growth rate (i.e., is the least efficient for large inputs)?

A) $O(\log N)$
B) $O(N)$
C) $O(N \log N)$
D) $O(N^2)$

4. Analyze the following Python snippet.

def another_function(data):
    N = len(data)
    # Loop 1
    for i in range(N):
        print(i)
    # Loop 2
    for j in range(N):
        print(j)

What is the Big $O$ time complexity of `another_function`?

A) $O(N^2)$
B) $O(2N)$
C) $O(N)$
D) $O(\log N)$

KEY TIPS

💡 Key Tips

Drop Non-Dominant Terms

Always simplify by keeping only the fastest-growing term.

O(N^2 + 50N + 100)

simplifies to

O(N^2)

Ignore Constants

The quiz is a perfect example! The inner loop runs 5 times, making the total operations

5 \times N

. We drop the constant 5, resulting in

O(N)

Worst-Case Focus

Big

O

provides an upper bound. It's a guarantee that the algorithm's performance will not exceed this rate of growth.

Logarithmic Clue

If an algorithm repeatedly halves the input data size in each step, its complexity is likely

O(\log N)

. Think Binary Search.

Defining Time Complexity: The Big OOO Notation

Big OOO Calculation Cheat Sheet

Standard Time Complexity Classes

Defining Time Complexity: The Big $O$ Notation

Big $O$ Calculation Cheat Sheet